Efficient Distance Metric Learning by Adaptive Sampling and Mini-Batch Stochastic Gradient Descent (SGD)

摘要

Distance metric learning (DML) is an important task that has foundapplications in many domains. The high computational cost of DML arises fromthe large number of variables to be determined and the constraint that adistance metric has to be a positive semi-definite (PSD) matrix. Althoughstochastic gradient descent (SGD) has been successfully applied to improve theefficiency of DML, it can still be computationally expensive because in orderto ensure that the solution is a PSD matrix, it has to, at every iteration,project the updated distance metric onto the PSD cone, an expensive operation.We address this challenge by developing two strategies within SGD, i.e.mini-batch and adaptive sampling, to effectively reduce the number of updates(i.e., projections onto the PSD cone) in SGD. We also develop hybrid approachesthat combine the strength of adaptive sampling with that of mini-batch onlinelearning techniques to further improve the computational efficiency of SGD forDML. We prove the theoretical guarantees for both adaptive sampling andmini-batch based approaches for DML. We also conduct an extensive empiricalstudy to verify the effectiveness of the proposed algorithms for DML.